package com.yuan.algorithms.base01;

import java.util.Scanner;

/**
 * @author YouYuan
 * <br>E-mail:1265161633@qq.com
 * <br>创建时间：2015年10月14日 下午7:12:47
 * <br>说明:N个人从1到N编号，围坐成一个圈，从1号开始传递一个热土豆，经过M次传递后拿着热土豆的人被清除离座，由坐在被清除的人后面的一个人
 *         	拿起土豆继续进行游戏。最后剩下的人获胜。给你N和M，请编写程序计算最后获胜的人。要求使用链表实现，要确保各个单元能够清除。
 */
class Node{
	Object element;
	Node nextNode;
	Node preNode;
}
class LinkedList{

	private int length;
	private Node head;//头节点
	private Node tail;//尾节点
	private Node current;//当前节点
	
	public LinkedList() {
		length = 0;
		head = tail = current = null;
	}
	
	public Node getHead() {
		return head;
	}

	/**
	 * 在链表尾部添加元素
	 * @param i
	 */
	public void add(Object i) {
		Node data = new Node();
		if (head==null) {
			head = tail = data;
		} else {
			current.nextNode = data;
			data.preNode = current;
			data.nextNode = head;
			tail = data;
			head.preNode = tail;
		}
		data.element = i;
		current = data;
		++length;
	}

	public int length() {
		return length;
	}

	public Node delete(Node current) {
		Node temp = current;
//		Node temp = head;
//		for (int i = 0; i < length; i++) {
//			if (!temp.equals(current)) {
//				temp = temp.nextNode;
//			} else {
//				break;
//			}
//		}
		if (temp.equals(current)) {
			temp.preNode.nextNode = temp.nextNode;
			temp.nextNode.preNode = temp.preNode;
			if (temp.equals(head)) {
				head = temp.nextNode;
			} else if (temp.equals(tail)) {
				tail = temp.preNode;
			}
			--length;
			return current.nextNode;
		}
		return current;
	}
}

public class 链表_Josephus问题 {

	
	static Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		while(in.hasNext()) {
			int n = in.nextInt();
			int m = in.nextInt();
			link(n, m);//链表模拟，较快
		}
	}
	
	private static void link(int n, int m) {
		LinkedList link = new LinkedList();
		for (int i = 1; i <= n; i++) {
			link.add(i);
		}
		Node current = link.getHead();
		while(link.length()!=1) {
			for (int i = 0; i < m; i++) {
				current = current.nextNode;
			}
			current = link.delete(current);
		}
		System.out.println(link.getHead().element);
	}

}
